package com.csx.tree;

import java.util.TreeMap;

/**
 * @author 陈胤训
 * @date 2019/6/5 14:46
 * Utils: Intellij Idea
 * Description: 字典树  单词查找树
 */
public class Trie {

    private class Node{

        /**
         * 是否为最后一个字符
         */
        public boolean isWord;

        /**
         * 下一个映射字符
         */
        public TreeMap<Character, Node> next;

        public Node(boolean isWord) {
            this.isWord = isWord;
            this.next = new TreeMap<>();
        }

        public Node() {
            this(false);
        }
    }

    /**
     * 根节点
     */
    private Node root;

    /**
     * 大小
     */
    private  int size;

    public Trie() {
        this.root = new Node();
        this.size = 0;
    }

    /**
     * 获取Trie中存储的单词数量
     * @return 大小
     */
    public int getSize(){
        return size;
    }

    /**
     * 向trie中添加一个新的单词word
     * @param word 单词
     */
    public void add(String word){
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.next.get(c) == null){
                cur.next.put(c,new Node());
            }
            cur = cur.next.get(c);
        }
        if (!cur.isWord){
            cur.isWord = true;
            size ++;
        }
    }

    /**
     * 向trie中添加一个新的单词word
     * @param word 单词
     */
    public void add1(String word){
        Node cur = root;
        add1(cur, word, 0);
    }

    /**
     * 向trie中添加一个新的单词word
     * @param word 单词
     */
    public void add2(String word){
        Node cur = root;
        root = add2(cur, word, 0);
    }

    private void add1(Node cur, String word, int index) {
        if (index == word.length()){
            if (!cur.isWord){
                cur.isWord = true;
                size ++;
            }
        }
        if (word.length() > index) {
            char c = word.charAt(index);
            if (cur.next.get(c) == null){
                cur.next.put(c, new Node());
            }

            add1(cur.next.get(c), word, index + 1);
        }


    }

    private Node add2(Node cur, String word, int index) {
        if (index == word.length()) {
            if (!cur.isWord) {
                cur.isWord = true;
                size++;

            }
        } else {
            char c = word.charAt(index);
            if (cur.next.get(c) == null) {
                cur.next.put(c, new Node());
            }

            cur.next.put(c, add2(cur.next.get(c), word, index + 1));

        }
        return cur;
    }

    /**
     * 查找单词word是否在Trie中
     * @param word 单词
     * @return true存在  false 不存在
     */
    public boolean contains(String word){
        Node cur= root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (cur.next.get(c) == null){
                return false;
            }
            cur = cur.next.get(c);
        }
        return cur.isWord;
    }


    /**
     * 查找单词word是否在Trie中  递归实现
     * @param word 单词
     * @return true存在  false 不存在
     */
    public boolean contains1(String word){
        Node cur = root;
        return contains1(cur, 0, word);
    }

    private boolean contains1( Node cur, int index, String word){
        if (index == word.length()) {
            return cur.isWord;
        }
            char c = word.charAt(index);
            if (cur.next.get(c) == null) {
                return false;
            }else{
                return  contains1(cur.next.get(c), index + 1, word);
            }
    }

    /**
     *  查询是否在Trie中有单词 以prefix为前缀
     * @param prefix 前缀
     * @return  true存在  false 不存在
     */
    public boolean isPrefix(String prefix){
        Node cur= root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (cur.next.get(c) == null){
                return false;
            }
            cur = cur.next.get(c);
        }
    return true;
    }

    public boolean search(String word){
        return match(root, word, 0);
    }

    private boolean match(Node root, String word, int index) {
        if (index == word.length()) {
            return root.isWord;
        }
        char c = word.charAt(index);
        if (c != '.'){
            if (root.next.get(c) == null) {
                return false;
            }else{
                return  match(root.next.get(c), word, index + 1);
            }
        }else{
            for (char nextChar : root.next.keySet()){
                if (match(root.next.get(nextChar), word, index + 1)){
                    return true;
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
//        trie.add("abcdefg");
//        trie.add("abc");
//        trie.add("def");
//        trie.add("efg");
//        System.out.println(trie.contains("abc"));
        //        System.out.println(trie.contains1("bcd"));
        trie.add2("abc");
        trie.add2("ab");
        System.out.println(trie.contains1("a"));
        System.out.println(trie.contains1("ab"));
        System.out.println(trie.contains1("abc"));

    }
}
